# class Treenode:
#     def __init__(self, val):
#         self.val = val
#         self.left = None
#         self.right = None
#
# import sortedcontainers
# class Solution(object):
#     def maxDepthBST(self, order):
#         d = {}
#         l = sortedcontainers.SortedList()
#         tree = Treenode(order[0])
#         d[order[0]] = tree
#         l.add(order[0])
#         for num in order[1:]:
#             new_node = Treenode(num)
#             index = l.bisect_right(num)
#             d[num] = new_node
#             if index > 0 and not d[l[index - 1]].right:
#                 d[l[index - 1]].right = new_node
#             else:
#                 d[l[index]].left = new_node
#             l.add(num)
#
#         dist = 0
#         st = [tree]
#         while st:
#             next_st = []
#             dist += 1
#             for node in st:
#                 if node.left:
#                     next_st.append(node.left)
#                 if node.right:
#                     next_st.append(node.right)
#             st = next_st
#         return dist

# O(n)解法
class Solution:
    def maxDepthBST(self, order) -> int:
        n = len(order)
        father, occur, stack = [0] * (n + 1), [0] * (n + 1), []
        for i, x in enumerate(order, 1): occur[x] = i
        for i, x in enumerate(occur):
            while stack and occur[stack[-1]] > x:
                if occur[father[stack[-1]]] < x:
                    father[stack[-1]] = i
                stack.pop()
            if stack and occur[father[i]] < occur[stack[-1]]:
                father[i] = stack[-1]
            stack.append(i)
        print(father)
        for x in order:
            father[x] = 1 + father[father[x]]

        return max(father)

data = Solution()
order = [8, 4, 3, 9, 6, 7, 10, 5, 1, 2]
print(data.maxDepthBST(order))
